In recent years, development of solid-state drives (SSDs) has been seen great progress, such SSDs using NAND flash memories (hereinafter sometimes simply referred to as flash memories) as rewritable nonvolatile memories.
In a flash memory, data is written in units of pages, whereas data is erased in units of blocks. Furthermore, before rewriting, data erase processing needs to be performed on a storage area to be rewritten.
With this property of the flash memory, as the data in the flash memory is progressively rewritten, invalid data (which is not the latest data) serves to increase the rate of storage areas in each block in which valid data cannot be stored. Thus, the SSD performs compaction processing in order to effectively utilize the storage areas in each block.
The compaction processing collects valid data from blocks in which storage areas with valid data stored therein have a reduced density, and rewrites the data to another block. The compaction target blocks are recovered as effectively available storage areas by erase processing performed after the rewrite processing.
For the compaction processing, it is important to increase the efficiency of search processing of searching for compaction source blocks and valid data in the blocks (for example, in units of clusters). Time required for the search processing significantly affects the performance of the SSD, thus requiring a technique for reducing the time required for the search processing. A reduction in the time required for the search processing enables an increase in the efficiency of the compaction processing.